Memory management among processes is an important task supported by most modern operating systems. The task of memory management involves several aspects, one of which is memory allocation within a process. Memory requests are satisfied by allocating blocks of memory (hereinafter “blocks”) from a large pool of memory called a heap. Although heap management, a form of memory allocation, is typically directed by a computer's operating system and accessed via standard interfaces, many programs may still need to manage dynamic memory allocation themselves, especially in shared memory, multi-process systems. Some solutions use a single large block and then fulfill requests for memory by dividing that block and returning the block requested to the requestor. When the requestor returns the block back, it is subsequently merged with a neighboring free block, if they are immediately adjacent, or inserted into a free list of currently free blocks. A free list is a data structure used in a scheme for dynamic memory allocation and operates by connecting unallocated regions of memory together in a linked list, using the first word of each unallocated region as a pointer to the next.
The time that it takes to find a suitably sized block to fulfill a request for memory, or to check for an adjacent block when a block is given back as free memory increases as free memory becomes fragmented into small discontinuous chunks.
Other solutions augment the single free list of variable sized blocks, with an additional set of free lists, where each list contains only blocks of the same fixed size. Populating the fixed size lists on demand requires that early requests for memory are served much as they would have been in the original case. However, as time goes on and the fixed size blocks are returned to their corresponding free list, more and more requests for memory will be served from the fixed size lists where allocation and deallocation can be completed with few pointer resets and no searching of linked lists.
Since the blocks on the fixed size list were originally requested by a process, it suggests that blocks of that size may be needed again in future by that particular process. However, if there is no requestor for blocks of a particular size, the fixed sized lists that include blocks of that size can have unused blocks that are not available for other processes.